import java.util.Random;

/*
题目描述：复杂链表的复制
复杂链表：每个节点不光有指向下一个节点的指针，还有指向任意节点的指针(包括null)
方法：
分别为每个节点进行复制，并将其放在源节点的后面，然后设置subling指针，最后拆分成两个链表
1. 复制
2. 设置subling指针
3. 拆分
 */
public class E35 {
    public static void main(String[] args) {
        RandomListNode node = new RandomListNode(1);
        node.next = new RandomListNode(2);
        node.next.next = new RandomListNode(3);
        node.next.next.next = new RandomListNode(4);
        node.next.next.next.next = null;
        node.random = node.next.next;

        RandomListNode res = Clone(node);
        while(res != null){
            System.out.print(res.label + "->");
            res = res.next;
        }
        System.out.println("null");
    }

    public static RandomListNode Clone(RandomListNode pHead){
        CloneNodes(pHead);
        ConnectSiblingNodes(pHead);
        return ReconnectNodes(pHead);
    }

    public static void CloneNodes(RandomListNode pHead){
        RandomListNode pNode = pHead;
        while(pNode != null){
            RandomListNode pCloned = new RandomListNode();
            pCloned.label = pNode.label;
            pCloned.next = pNode.next;
            pCloned.random = null;

            pNode.next = pCloned;
            pNode = pCloned.next;
        }
    }

    public static void ConnectSiblingNodes(RandomListNode pHead){
        RandomListNode pNode = pHead;
        while(pNode != null){
            RandomListNode pCloned = pNode.next;
            if(pNode.random != null){
                pCloned.random = pNode.random.next;
            }
            pNode = pCloned.next;
        }
    }

    public static RandomListNode ReconnectNodes(RandomListNode pHead){
        RandomListNode pNode = pHead;
        RandomListNode pClonedHead = null;
        RandomListNode pClonedNode = null;

        if(pNode != null){
            pClonedHead = pClonedNode = pNode.next;
            pNode.next = pClonedNode.next;
            pNode = pNode.next;
        }
        while(pNode != null){
            pClonedNode.next = pNode.next;
            pClonedNode = pClonedNode.next;
            pNode.next = pClonedNode.next;
            pNode = pNode.next;
        }
        return pClonedHead;
    }
}


class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }

    RandomListNode(){

    }
}